% simulation.tex: Simulator usage, built-in routines
%
% Author: Marcel van der Goot
%
% $Id: simulation.tex,v 1.5 2002/12/15 19:34:29 marcel Exp $
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\chapter{Simulation}\label{chap:simulation}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Command line arguments}\label{sec:cmndline}

The \verb|chpsim| program takes the following command line arguments.

\begin{description}
\item[{\it{}source\_file}] \ \linebreak
The top-level module. Only one source file is
specified on the command line; other modules are read based on \verb|requires|
clauses.

\item[{\tt{}-main} {\it{}process}] \ \linebreak
The execution starts with one instance of this
process. This must be a process without meta parameters and port parameters.
If no \verb|-main| option is specified, the initial process is {\it{}main}.

\item[{\tt{}-I} {\it{}directory}] \ \linebreak
Appends the directory to the module search path.
If module {\it{}A} has a \verb|requires "|{\it{}B}\verb|"| clause, the simulator first looks for
{\it{}B} in the directory where it found {\it{}A}. If {\it{}B} is not found in that
directory, the simulator checks each of the directories in the search
path, in order. The search path does not apply to the top-level module,
nor does it apply if {\it{}B} is an absolute path name or starts with `\verb|.|' or
`\verb|..|'. See also the \verb|-v| option.

\item[{\tt{}-I-}] \ \linebreak
Clears the search path.

\item[{\tt{}-C} {\it{}command} [{\it{}args} ...]] \ \linebreak
Execute the given command before user
interaction.  Multiple \verb|-C|'s can be specified, which will execute the commands
in the order listed.  All arguments following the \verb|-C|, until the next
argument starting with \verb|-|, are treated as the command and its argument, so it
is a good idea to specify the {\it{}source\_file} before any such commands.
This option is most useful in conjunction with the source command
(Section \ref{sec:othercmnd}).

\item[{\tt{}-batch}] \ \linebreak
By default an interactive session is started, as described
in Section \ref{sec:exec}. With this option, the simulator executes the whole
program without stopping for user commands.  Any \verb|-C| arguments present
will still be executed.

\item[{\tt{}-q}] \ \linebreak
This option also disables the interactive session, but rather than executing
the program, \verb|chpsim| will terminate.  Any \verb|-C| arguments present
will still be executed (this option would be rather pointless otherwise).

\item[{\tt{}-log} {\it{}file}] \ \linebreak
A copy of all user commands and simulator output
is written to this file. When \verb|-batch| is used, the default log file is
{\it{}stderr}. (The log file only applies to simulator output, not to output
generated by the CHP program; see the \verb|-stdout| option.)

\item[{\tt{}-stdout} {\it{}file}, {\tt{}-o} {\it{}file}] \ \linebreak
Specifies the file to use for the {\it{}print} and {\it{}show}
procedures described in Section \ref{sec:builtin}, and for {\it{}stdout} defined
in Section \ref{sec:stdio}. The default is the standard output.

\item[{\tt{}-v}] \ \linebreak
Prints version information, the search path, and the name
of each file that is read.

\item[{\tt{}-trace} {\it{}instance}] \ \linebreak
Trace this instance, in the same way as
the \verb|trace| command of Section \ref{sec:trace}. This is useful with the
\verb|-batch| option (you probably also want to use \verb|-log|). Instance names
are described in Section \ref{sec:exec}; they always start with a `/'.

\item[{\tt{}-traceall}] \ \linebreak
Trace all process instances. This will generate a
lot of output for anything but the shortest programs. In most cases,
judiciously placed breakpoints are more helpful.

\item[{\tt{}-watchall}] \ \linebreak
Watch all wires.  This is equivalent to executing the \verb|watch| command in
Section \ref{sec:trace} for every single wire in the program. Again, this will
usually produce too much data to be helpful.

\item[{\tt{}-timed}] \ \linebreak
Usually \verb|chpsim| executes commands in a random order to ensure that the
design does not contain any race conditions.  This option will instead run the
simulation with a very simple timing model that can be used to get a rough
idea of the circuit's performance.  Note that by default, this timing model
will execute as many CHP threads as possible before simulating a single
production rule, which can lead to ``livelock''.

\item[{\tt{}-seed}] \ \linebreak
Specify a specific seed for the random number generator that controls the
thread execution order and the \verb|random| function
(Section \ref{sec:builtin}).  By default this seed is set to zero, so that
multiple runs of the same program will produce identical results.

\item[{\tt{}-timeseed}] \ \linebreak
Set the random number generator seed to the value of the current system clock.
The seed used will be reported at the beginning of operation so that the run
can be repeated if necessary.

\item[{\tt{}-critical}] \ \linebreak
This flag turns on tracking of critical timing paths, enabling the use of the
\verb|critical| command described in Section \ref{sec:othercmnd}.  This option implies
the \verb|-timed| option.

\item[{\tt{}-nohide}] \ \linebreak
Normally, when \verb|chpsim| uses a value union to connect two ports of
different type, and the conversion between these types is specfied via a
process instead of a function, \verb|chpsim| will hide the instance of
the process that converts between the two types from the various debugging
commands.  This option will simply treat them like any other instance.

\item[{\tt{}-strict}] \ \linebreak
This turns on strict checking for illegal variable sharing.  The syntax of
CHP itself makes sharing a variable between seperate processes impossible,
but it doesn't prevent sharing a variable between threads of a single process.
Sometimes \verb|chpsim| catches these errors, sometimes the error will pass
unnoticed, and sometimes \verb|chpsim| will end up in a very odd state that
makes it hard to track down the source of the error.  Strict checking will
report all illegal variable sharing, and no program should be considered
correct if it cannot pass strict checking.  However, strict checking can
significantly slow down large simulations, so it is not on by default.
\end{description}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Execution}\label{sec:exec}

At any time, the simulator executes a number of threads in parallel.
Typically, there is one thread per process instance, but if a process
executes a parallel statement (statements separated by commas), it will
temporarily have multiple threads. Each thread can be active (ready) or suspended.
The simulator's \verb|print| will, for each instance, list the current number of
active and suspended threads:
\medskip
\hrule
\begin{verbatim}
(cmnd?) print
  /q[0]/r: 1 active threads
  /tgt: 1 active threads
  /src: 1 suspended threads
\end{verbatim}
\hrule
\medskip
The example shows that the three process instances of this example have
a total of three threads.
The names starting with a slash are hierarchical
instance names, constructed from the identifiers in instance declarations
(Section \ref{sec:instance}). The initial process has as name merely a slash.
Hence, \verb|/q[0]/r| is instance \verb|r| created by \verb|/q[0]|, which itself was
instantiated by the initial process.
An indication like \verb|example.chp[42:2]|
gives, respectively, the source file, the line number, and the position on the
line, of the statement that will be executed next by the thread.

The simulator executes one (non-composite) CHP statement at a time, chosen from
among the active threads. Execution is fair: an active statement will
eventually be executed; a suspended statement will eventually be checked
to determine whether it can be made active again.

The simulation consists of two phases, the instantiation phase and
the execution phase. The simulation starts by creating a single instance
of the initial process. Typically, this is a meta process that instantiates
other (child) processes. As explained in Section \ref{sec:meta}, child processes
only start executing when their parent process has terminated. Furthermore,
CHP processes only start executing when all meta processes have
terminated, which is the end of the instantiation phase. (The initial
process may be a CHP process, in which case the execution phase
starts immediately.)

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{The current statement}\label{sec:currstmt}

When the simulator stops to allow input of a command, it will print something
similar to the following two lines:
\medskip
\hrule
\begin{verbatim}
(break) /q[0]/r at example.chp[42:2]
	x[i] := true
\end{verbatim}
\hrule
\medskip
The first line starts with the reason that the simulator has stopped for
input (in this case, a breakpoint was reached).  Next on the line is the
instance to which the current thread belongs, followed by the exact
position in the code of the statement that the thread is on.  This
position is specified first by the name of the file it is in, then the
line number of the statement, and finally, the exact line position of the
first character of the statement.  The second line printed is a copy of
the statement itself.

The statement that is printed here is known as the current statement.
Aside from when simulation is stopped due to an error or warning, this
is the statement that will be executed next by thread.  The current
statement also has the ``focus'', meaning that it is used as a reference
point for most of the simulator commands. When no process instance is mentioned,
most commands apply to the current statement or the current instance.
Some commands allow you to select an instance explicitly. For convenience,
several of the simulator commands (such as \verb|trace|) allow
you to reference process instances that have not yet been created.

The \verb|view|, \verb|up|, and \verb|down| commands let you change the instance and statement
that have the focus. This is mainly useful when you want to print
variable values (because variables must be in scope), but also changes
the default focus for the other simulator commands. However, these commands
never affect the actual order of execution: the next statement is the
original current statement. See Section \ref{sec:inspect} for more details.

Commands may be abbreviated, usually to a single letter.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Steps}\label{sec:steps}

The simulator repeatedly executes statements, or steps, until there is a
reason to ask for command input. The simulator stops at the beginning of
the instantiation phase, and at the beginning of the execution phase.
When the simulator is stopped, you can enter commands to inspect
variables, to set breakpoints, etc.. To make
the simulation continue, you must enter one of the three commands
\verb|step|, \verb|next|, or \verb|continue|. An empty command is equivalent to one
of these three, depending on what made the simulator stop: if the simulator
stopped because of a \verb|step| or \verb|next| command, that is also the default;
in all other cases the default is \verb|continue|.

The \verb|step| command tells the simulator to execute one step, i.e., one
statement, of the current process. This is the statement printed before
the command prompt. For instance:
\medskip
\hrule
\begin{verbatim}
(step) /src at example.chp[63:17]
        p!n
(cmnd?) 
\end{verbatim}
\hrule
\medskip
The current process is \verb|/src|, which is about to execute \verb|p!n|. Entering
\verb|step| (or, in this case, an empty command) allows execution of \verb|p!n|,
and forces a stop at the next statement of \verb|/src|. The \verb|step| command
refers to the current process only: between the current step and the
next stop, there may be multiple execution steps of other processes.

The \verb|next| command is nearly the same as the \verb|step| command, but it
treats function and procedure calls as a single step. I.e., if the
current statement is a procedure call, \verb|next| will stop at the statement
after the call, whereas \verb|step| will stop at the first statement of
the called procedure.

The \verb|step| and \verb|next| commands can take an instance name as argument.
In that case the simulator will stop when it reaches the next statement
of that process instance.

The \verb|continue| command continues execution until there is reason to
stop again, such as a breakpoint.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Execution of functions}\label{sec:functionexec}

Since expressions are always part of a statement, execution of a
statement as a single step implies that expression evaluation is atomic.
However, this poses a problem for function evaluation: a function call
is part of an expression, hence atomic, yet its evaluation consists
of multiple statements. The simulator solves this by executing the
function in isolation: while executing the function, it ignores all other
threads until the function has finished. Since functions do not interact
with other threads, their atomicity is actually a non-issue; it
is mentioned only because it can be observed in the simulator.

Function calls with constant arguments are themselves constant (Section
\ref{sec:funccall}). You may observe that such a call is indeed executed
only once.

Procedure calls are statements, and are therefore treated like other
composite statements: they are not atomic.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Breakpoints}\label{sec:breakpoint}

The \verb|break| command sets a breakpoint. Whenever execution reaches a breakpoint,
the simulator stops to allow command input. Breakpoints may be associated
with a just a statement in the code, or with a particular instance as well as a
statement.  However, each statement may have at most one breakpoint attached to it.

By itself, \verb|break| sets a breakpoint at the current statement.  This will
not be tied to the current instance.

The following form of \verb|break| sets a breakpoint at the statement at or
near the indicated position.
\begin{verbatim}
break "filename" linenumber : position
\end{verbatim}
Only the line number is required. If a file name is specified,
it must be between quotes. If a position on the line is specified, it must
be preceded by a colon.

This third form of \verb|break| sets a breakpoint associated with one
particular instance.
\begin{verbatim}
break instance linenumber : position
\end{verbatim}
The given line number and position must refer to a statement that is part
of the process definition that is connected to the given instance.

All three of the above commands can be followed by ``\verb|if| {\it condition}'',
where {\it condition} can be any expression that evalutes to a boolean and is
valid in the reference frame of the breakpoint.  Adding this construct will only
allow the breakpoint to be tripped when {\it condition} evaluates to \verb|true|.

A fourth form of \verb|break| sets a breakpoint at the beginning of the
specified routine (a process, procedure, or function).
\begin{verbatim}
break "filename" routine
\end{verbatim}
Again, the file name is optional. If the routine is not a top-level routine,
you can use a dot to construct a hierarchical name: use \verb|break g.f| to stop
at function \verb|f| which is declared inside procedure \verb|g|. A file name need
only be specified if otherwise the top-level routine name is not unique.

To remove a breakpoint, use the \verb|clear| command instead of the \verb|break|
command with any of the above forms.  The \verb|clear| command will clear
whatever breakpoint is at the specified statement, regardless of whether it has
a condition or is tied to a given instance, and regardless of whether the
\verb|clear| command specfifes a single instance (\verb|clear| is not allowed
to specify a condition).  Once a statement has a breakpoint set to it, the only
way to modify the breakpoint is to clear it and set it again.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Tracing}\label{sec:trace}

When a process instance is traced, the simulator prints every statement
executed by that instance, without stopping (unless there is another
reason to stop).

\verb|trace| by itself starts tracing the current process instance. If an
instance name is specified, that instance will be traced.

A process that has production rules cannot be traced.  Instead, such a process
can have a watch placed on any or all of its wires.  This will result in the
simulator printing out a notfication any time that a watched wire changes value.
The command to set a watch is \verb|watch| {\it expression}, where
{\it expression} is a standard expression that is valid in the current frame
of reference and evaluates to a wire (i.e. would be valid as the target of a
production rule).  Watching the wires of a given instance requires first setting
the focus to that instance, and each wire must be listed in a seperate
\verb|watch| command.

To stop watching a  wire, use \verb|clear watch| {\it expression}, with the
restrictions on {\it expression} as above.
To stop tracing, use \verb|clear trace|, optionally followed by an instance
name. \verb|clear step| {\it instance} can also be used to cancel
a pending \verb|step| or \verb|next| for a given process (i.e., execution will not
stop when the next statement of that process is reached).  The \verb|clear|
command cannot undo the effects of the command line arguments \verb|-traceall|
and \verb|-watchall|.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Inspecting the state}\label{sec:inspect}

The \verb|where| command prints the current call stack, i.e., the sequence
of nested procedure and function calls that led to the current statement.
You can move the focus up or down this stack with the \verb|up| and \verb|down|
commands (both take an optional number of steps as argument). The `up'
direction is towards the caller. Moving the focus is useful when you
want to print variables, because only variables of the current routine
are visible.

You can shift the focus to a different process with the \verb|view| command.
(Without argument this simply prints the current statement.) Again, this
is useful if you want to print variables of that process. As mentioned
before, changing the focus changes the default process for commands
like \verb|step|; however, it does not change the actual scheduling of statements.

The \verb|print| command by itself shows all existing threads.

\verb|print| followed by an instance name prints the values of the instance's
meta parameters, the other processes the instance is connected to,
and the current position in the code for each thread of the process.

\verb|print| followed by a variable or constant name prints the value of that
variable or constant. The name must be in scope at the current focus.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Other commands}\label{sec:othercmnd}

The \verb|help| command prints a command summary.

The \verb|source| command takes a filename as an argument, and executes
the list of commands contained in the file.

The \verb|batch| command switches to non-interactive execution, without stopping
for more user input, just like the \verb|-batch| option described in Section
\ref{sec:cmndline}.

Interrupting the program with \verb|ctrl-C| forces the simulator to stop
at the next statement, regardless of the instance. This is useful if
the program gets stuck in an infinite or very long loop. (In batch mode,
\verb|ctrl-C| simply terminates the simulation.)

The simulator also stops immediately after a statement that
caused a warning or error message, so that you can inspect variables etc..
The computation cannot continue following an error; instead, the simulator
will terminate.

The \verb|quit| command also terminates the simulation.

The commands \verb|fanin| and \verb|fanout| allow for the inspection of
which production rules are associated with a given wire.
Each requires an expression as an argument that must evaluate to a single wire.
\verb|fanin| lists in full all production rules which target a given wire
(there will be at most two).  \verb|fanout| lists an abbreviated form of each
production rule where the given node is part of the rule's guard.  Any threads
which are waiting for the wire value to change are also listed.

The \verb|critical| command will list the critical timing path of the most
recent transition of a given wire.  A critical timing path goes from one
production rule firing to whatever event caused the guard of the production
rule to become true, and repeats this step as long as the event is also a
production rule firing.  Typically, the critical timing paths of all wires
will converge to the same path, and this path will usually repeat itself if
the simulation goes on for long enough.  The repeating portion of such a
path is called the critical cycle.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Instantiation}\label{sec:instantiation}

%\verb|meta|

During instantiation additional commands are available.  The purpose of these
commands is to replace the large collection of processes produced by a meta
process with a single sequential chp process.  Of course, this can only be done
if the meta process has the optional chp body specified.

The \verb|instantiate| command
takes an instance name as an arguments, and completes the instantiation of only
this process.  If no argument is given, the current process is chosen.  In order to
function correctly, the instantiate command must specify a process that is listed
via the \verb|print| command, in other words one whose parent has completed
instantiation.  Thus, to instantiate the meta process {\it{}/cpu/fetch}, we run:
\begin{verbatim}
instantiate /
instantiate /cpu
instantiate /cpu/fetch
\end{verbatim}

The command \verb|continue sequential| is a special command that completes the
instantiation phase.  However, only meta processes that have already begun
instatiation, or that do not have an optional chp body specified will be
instantiated.  In other words, after specifying which processes need to be
instantiated as meta bodies, \verb|chpsim| completes instantition using as few
additional processes as possible.




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Built-in procedures}\label{sec:builtin}

The simulator has a few built-in procedures that can be called from
your CHP program to help with testing and debugging. These are
always available, unless you have redefined the identifiers.

\begin{verbatim}
procedure step()
\end{verbatim}
This routine executes the simulator's \verb|step| command. The effect is that
the simulator will stop at the next statement of the process that made the
call. (Hence, this acts more or less as a permanent breakpoint.)

\begin{verbatim}
procedure print(...)
\end{verbatim}
This procedure can be passed any number of arguments. It prints its argument
values on the standard output, followed by a newline. E.g.,
\begin{verbatim}
x := 5; y := red;
print("x and y are", x, y);
\end{verbatim}
results in
\begin{verbatim}
/q[0]/r> x and y are 5 red
\end{verbatim}
where process instance \verb|/q[0]/r| executed the \verb|print| call.

\begin{verbatim}
procedure show(...)
\end{verbatim}
This procedure prints its arguments with their values:
\begin{verbatim}
show(x+1, y)
\end{verbatim}
prints
\begin{verbatim}
/q[0]/r> example.chp[7:3] 
        x + 1 = 6
        y = red
\end{verbatim}
Note that it also indicates the location of the call.

\begin{verbatim}
procedure warning(...)
procedure error(...)
\end{verbatim}
These cause a warning and error, respectively, with the argument values
as message (in the same way as \verb|print()|).

\begin{verbatim}
procedure assert(cond: bool)
\end{verbatim}
Causes an error if the condition is \verb|false|.

\begin{verbatim}
function random(N: int)
\end{verbatim}
Return a random integer between $0$ and $N-1$.  This is for debugging only ---
if you want to implement a pseudo random number generator as part of your
design, you need to choose an algorithm and implement it in stantard CHP.

\begin{verbatim}
function time()
\end{verbatim}
Return the current elapsed simulation time.  Again, this is for debugging only
and is not the solution to timing assumption problems in your code.  Even for
debugging this should be used with care, since it can easily lead to
unintentional deadlock or livelock.  If random timing is enabled, the numbers
returned by \verb|time()| will be pretty much meaningless.

There is also a built-in type \verb|string|, which is an array of \verb|{0..127}|,
i.e., an array of ascii values. However, since no array bounds are specified,
you cannot index variables of this type. It is useful for some debugging
routines.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Standard I/O}\label{sec:stdio}

There is a standard module \verb|stdio.chp| that defines procedures for
reading and writing files. This module must be imported with \verb|requires| to
use these procedures. Obviously, this module is intended for testing and
debugging only.
\begin{verbatim}
type file
const stdin: file
const stdout: file
type file_err = { ok, eof, no_int };
\end{verbatim}
Opening and closing of files is done with
\begin{verbatim}
procedure fopen(res f: file; name: string; mode: string)
procedure fclose(f: file)
\end{verbatim}
The \verb|mode| argument is the same as for the \verb|fopen()| function in C. In
particular, \verb|"r"| opens the file for reading, \verb|"w"| opens the file for
writing (erasing the existing contents).

Reading is done with
\begin{verbatim}
procedure read_byte(f: file; res x: {0..255}; res err: file_err)
procedure read_int(f: file; res x: int; res err: file_err)
\end{verbatim}
\verb|read_byte| reads a single byte (character). If successful it sets \verb|err|
to \verb|ok|; otherwise it sets \verb|err| to \verb|eof| and \verb|x| to 0.

\verb|read_int| skips white space, then reads an integer written in the standard
CHP notation (Section \ref{sec:inttoken}). The integer may be immediately
preceded by a single minus sign. If no digit is found,
\verb|err| is set to \verb|no_int| (and \verb|x| to 0). At the end of the
file, \verb|err| is set to \verb|eof|.

Writing is done with
\begin{verbatim}
procedure write_byte(f: file; x: {0..255})
procedure write_string(f: file; x: string)
procedure write_int(f: file; x: int; base: {2..36})
procedure write(f: file; ...)
\end{verbatim}
\verb|write_byte| writes a single byte/character. \verb|write_string| writes
a sequence of characters, stopping if a 0 character is encountered (the 0
is optional).

\verb|write_int| writes an integer in the specified base. Decimal integers
are written without base, hexadecimal is written with \verb|0x|, and all
others are written with the {\it{}base}\verb|#| notation.

Finally, \verb|write| writes its arguments in the same way as the \verb|print|
procedure of Section \ref{sec:builtin}, but without the instance name.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

